package q1046_lastStoneWeight;

import java.util.PriorityQueue;

public class Solution {
    /*
    这里涉及到大顶堆，如果不考虑额外实现数据结构，则只需要使用优先队列即可
    首先创建一个优先队列 其排序规则按照从大到小排序 然后将所有石头加入其中
    当队中有超过一个元素时 不断的取出前两个 也就是当前最大的两个 考虑是否有差值 有则再次加入队列中
    最后考察队列是否为空 返回相应的结果即可
     */
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        for (int stone : stones) pq.offer(stone);

        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            if (a > b) pq.offer(a - b);
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }
}
